package november.recursion;

import java.lang.reflect.Array;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @author huangxin
 * @date 2019/11/16-12:28
 * 迷宫问题
 */
public class Maze {
    public static void main(String[] args) {


        //上右下左抽取成四个方法,定义数组  1上,2右,3下,4左
//       根据不同的顺序去执行, 接着循环找出0最多的数组,就是最快方法

        int[][] arr = {
                {4, 3, 2, 1},
                {3, 2, 1, 4},
                {2, 1, 4, 3},
                {1, 4, 3, 2},
                {1, 2, 3, 4},
                {2, 3, 4, 1},
                {3, 4, 1, 2},
                {4, 1, 2, 3}
        };

        List<int[][]> list = new ArrayList<>();
        for (int i = 0; i < arr.length; i++) {
            int[][] maze = getMaze();
            if (setWay(maze, 1, 1, arr[i])) {
                list.add(maze);

                //走的通的路线
                System.out.println(Arrays.toString(arr[i]));
                System.out.println(getWayLength(maze));
                printMaze(maze);
            }
        }
    }

    static void printMaze(int[][] maze) {
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[0].length; j++) {
                System.out.printf("%d\t", maze[i][j]);
            }
            System.out.println();
        }
        System.out.println();
    }

    //获取走过的路径
    static int getWayLength(int[][] maze) {
        int sum = 0;
        for (int i = 0; i < maze.length; i++) {
            for (int j = 0; j < maze[0].length; j++) {
                if (maze[i][j] == 2) {
                    sum++;
                }
            }
        }
        return sum;
    }

    static int[][] getMaze() {
        int[][] maze = new int[8][7];//8行7列

        //把迷宫四周设置为1
        for (int i = 0; i < maze[0].length; i++) {
            maze[0][i] = 1;//第一行
            maze[maze.length - 1][i] = 1;//最后一行
        }
        for (int i = 1; i < maze.length - 1; i++) {
            maze[i][0] = 1;//左边第一列
            maze[i][maze[0].length - 1] = 1;//右边最后一列
        }

        //设置障碍
        maze[3][1] = 1;
        maze[1][2] = 1;
        maze[5][5] = 1;
        maze[5][4] = 1;
        maze[3][5] = 1;
        maze[1][5] = 1;

//        for (int i = 0; i < maze.length; i++) {
//            for (int j = 0; j < maze[i].length; j++) {
//                System.out.printf("%d\t", maze[i][j]);
//            }
//            System.out.println();
//        }
//
//        setWay(maze, 1, 1);
//        System.out.println();
//
//        for (int i = 0; i < maze.length; i++) {
//            for (int j = 0; j < maze[i].length; j++) {
//                System.out.printf("%d\t", maze[i][j]);
//            }
//            System.out.println();
//        }

        return maze;
    }

    /**
     * 通过穷举求出最佳算法
     *
     * @param map
     * @param i
     * @param j
     * @return
     */
    public static boolean setWay(int[][] map, int i, int j, int[] arr) {
        if (map[6][5] == 2) {
            //终点==2,表示已经走通
            return true;
        } else {
            if (map[i][j] == 0) {
                //表示该点还没走过

                //标记走过该点
                map[i][j] = 2;

                for (int k = 0; k < arr.length; k++) {
                    switch (arr[k]) {
                        case 1:
                            if (top(map, i, j, arr)) {
                                return true;
                            }
                            break;
                        case 2:
                            if (right(map, i, j, arr)) {
                                return true;
                            }
                            break;
                        case 3:
                            if (bottom(map, i, j, arr)) {
                                return true;
                            }
                            break;
                        case 4:
                            if (left(map, i, j, arr)) {
                                return true;
                            }
                            break;
                    }
                }
                map[i][j] = 3;
                return false;

            } else {
                //如果已经走过,表示该点走不通
                return false;
            }
        }
    }


    /**
     * 如果到底 map[6][5]则表示通过
     *
     * @param map
     * @param i
     * @param j
     * @return
     */
    public static boolean setWay(int[][] map, int i, int j) {
        if (map[6][5] == 2) {
            //终点==2,表示已经走通
            return true;
        } else {
            if (map[i][j] == 0) {
                //表示该点还没走过

                //标记走过该点
                map[i][j] = 2;
                if (setWay(map, i, j + 1)) {//右
                    return true;
                } else if (setWay(map, i + 1, j)) {//下
                    return true;
                } else if (setWay(map, i, j - 1)) {//左
                    return true;
                } else if (setWay(map, i - 1, j)) {//上
                    return true;
                } else {
                    //走过,但没有走通 则为3
                    map[i][j] = 3;
                    return false;
                }
            } else {
                //如果已经走过,表示该点走不通
                return false;
            }
        }
    }

    public static boolean left(int[][] map, int i, int j, int[] arr) {
        return setWay(map, i, j - 1, arr);
    }

    public static boolean right(int[][] map, int i, int j, int[] arr) {
        return setWay(map, i, j + 1, arr);
    }

    public static boolean top(int[][] map, int i, int j, int[] arr) {
        return setWay(map, i - 1, j, arr);
    }

    public static boolean bottom(int[][] map, int i, int j, int[] arr) {
        return setWay(map, i + 1, j, arr);
    }


}
